package List;

public class MyLinkedList implements SeqList{
    private int size;
    private Node head;

    private static class Node {
        private int val;
        private Node next;
        public Node(int val) {
            this.val = val;
        }
    }

    //头插
    public void addFirst(int val){
        Node node = new Node(val);
        node.next = head;
        head = node;
        size++;
    }

    //尾插
    @Override
    public void add(int val) {
        add(size,val);
    }

    @Override
    public void add(int index, int val) {
        if(index<0||index>size){
            throw new IllegalArgumentException("add index illegal");
        }
        if(index==0){
            addFirst(val);
            return;
        }
        Node node = new Node(val);
        Node prev = head;
        for (int i = 0; i <index-1 ; i++) {
             prev = prev.next;
        }
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    @Override
    public boolean contains(int val) {
        for(Node x = this.head;x!=null;x=x.next){
            if(x.val==val){
                return true;
            }
        }
        return false;
    }

    @Override
    public int get(int index) {
        if(!rangeCheck(index)){
            throw new IllegalArgumentException("get index illegal");
        }

        Node x = this.head;
        for (int i = 0 ;i<index;i++){
            x=x.next;
        }

        return x.val;
    }

    private boolean rangeCheck(int index) {
        if(index<0||index>=size){
            return false;
        }
        return true;
    }

    @Override
    public int set(int index, int newVal) {
        if(!rangeCheck(index)){
            throw  new IllegalArgumentException("set index illegal!");
        }
        Node x = this.head;
        for (int i = 0; i < index ; i++) {
            x = x.next;
        }
        int oldVal = x.val;
        x.val = newVal;
        return oldVal;
    }

    public int removeFirst(){
        return removeByIndex(0);
    }

    public int removeLast(){
        return removeByIndex(this.size-1);
    }

    @Override
    public int removeByIndex(int index) {
        if(!rangeCheck(index)){
            throw new IllegalArgumentException("remove index illegal!");
        }
        if(index==0){
            Node newHead = this.head.next;
            int val = this.head.val;
            this.head.next = null;
            this.head = newHead;
            size--;
            return val;
        }

        Node prev = this.head;
        for (int i = 0; i < index-1; i++) {
            prev = prev.next;
        }
        Node cur = prev.next;
        int val = cur.val;
        prev.next = cur.next;
        cur.next = null;
        size--;
        return val;
    }

    @Override
    public void removeByValOnce(int val) {
        if(this.head==null){
            return;
        }
        if(this.head.val==val){
            removeFirst();
            return;
        }
        Node prev = this.head;
        while (prev.next!=null){
            if(prev.next.val==val){
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next =null;
                size--;
                return;
            }
            prev = prev.next;
        }
    }

    @Override
    public void removeByValAll(int val) {
        if(this.head==null){
            return;
        }
        while (head!=null&&head.val==val){//判断从开头开头是不是要删的节点,一直删到为空或头节点不是要删的结点为止
            Node next = head.next;
            head.next=null;
            head=next;
            size--;
        }
        if(head==null){//判断链表删完没有
            return;//删完return
        }
        Node prev = head;//到此head节点不是要删的节点
        //删中间需删除的节点
        while (prev.next!=null){
            Node cur = prev.next;//prev是前驱,cur是当前节点
            if(cur.val==val){
                prev.next = cur.next;
                cur.next = null;
                size--;
            }else {//只有当前节点不是要删的节点前驱才往后走
                prev = prev.next;
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node cur = this.head;
        while (cur!=null){
            sb.append(cur.val);
            sb.append("->");
            if(cur.next==null){
                sb.append("NULL");
            }
            cur=cur.next;
        }
        return sb.toString();
    }
}
